package VacationHomework.LeetCode;

public class Num148 {
    public ListNode sortList(ListNode head) {
        if(head==null || head.next==null){
            return head;
        }
        ListNode slow=head;
        ListNode fast=head.next;
        while (fast!=null && fast.next!=null){
            slow=slow.next;
            fast=fast.next.next;
        }
        ListNode tmp=slow.next;
        slow.next=null;
        ListNode left=sortList(head);
        ListNode right=sortList(tmp);
        return merge(head,left,right);
    }

    private ListNode merge(ListNode head, ListNode left, ListNode right) {
        ListNode newHead=new ListNode(0);
        ListNode p=newHead;
        while (left!=null &&right!=null){
            if(left.val<right.val){
                p.next=left;
                left=left.next;
            }else {
                p.next=right;
                right=right.next;
            }
            p=p.next;
        }
        p.next=left!=null?left:right;
        return newHead.next;
    }
}
